\documentclass[12pt]{article}

\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\linespread{1.4}

\begin{document}

\title{\textbf{Let's Map The World}~\\--~\\Rapport de soutenance 1}
\author{~\\~\\Quentin \textsc{Cavalie} - cavali\_q~\\Zoé \textsc{Delduc} - delduc\_z~\\Hervé \textsc{Droit} - droit\_h~\\Kévin \textsc{Le-Dû} - le-du\_k}

\maketitle


\begin{center}
\includegraphics[scale=0.2]{quadrillage2.png}
%\caption{Page d'accueil du projet, accompagnée d'un rapide guide explicatif}
\end{center}


\newpage

\tableofcontents

\newpage

\section{Introduction}

Lors de notre première année à l'EPITA, nous avons eu l'occasion de développer un projet de notre choix sans grandes restrictions. Cependant, le sujet de ce nouveau projet nous est imposé. Nous devons donc concevoir et développer un logiciel de cartographie 3D
permettant de réaliser une modélisation tridimensionnelle d'une carte plane -- idéalement, scannée. Le langage imposé pour la partie obligatoire est l'OCaml, développé par des chercheurs français de l'INRIA, principalement destiné à des applications scientifiques. A cela s'ajoute le langage C, autorisé pour les bonus et simplement interfaçable avec l'OCaml.

Nos groupes respectifs de l’année dernière étant \textit{morts} -- pertes de membres,
redoublements -- depuis un petit moment, nous avons décidé de former un
nouveau groupe : LMTW. Ce groupe, promis à un brillant avenir, est formé de Kévin et Hervé, deux codeurs fous, de Quentin, un redoublant qui passait par là, et de Zoé, parce qu'avoir une fille dans le groupe, c’est mieux!

Ainsi, nous vous présentons aujourd’hui l’avancement de notre projet : \textbf{Let’s Map The World !}.

\newpage

\section{Interface graphique}

Nous avons profité de la semaine de conférences -- organisée début Septembre -- pour commencer à \textit{tâter} les différentes options pour mettre en place une interface graphique fonctionnelle et visuellement ergonomique.

\subsection{LablGTK}

Après quelques tests et recherches, nous avons décidé d’utiliser la librairie \textsc{LablGTK}, qui possède l'énorme avantage d’avoir une documentation relativement fournie, claire et bien conçue. Ainsi, nous avons amorcé le développement de l’interface ; le développement de la tâche s’est fait plutot rapidement, avant d'aboutir au résultat présenté lors de la première soutenance.

\begin{center}
\includegraphics[scale=1]{logolablgtk.png} 
\end{center}

LablGTK se révèle etre une librairie relativement puissante, notamment grâce à son concept de \textit{boxes}. En effet, les différents composants -- boutons, barres de chargement, zone de saisie, zone d'affichage graphique -- s'imbriquent dans des boites horizontales et verticales. Ainsi, si vous insérez deux boutons dans une boite verticale, ils seront disposés l'un au-dessus de l'autre ; et pareillement pour les boites horizontales.

Un agencement intelligent et réfléchi de ces modules permet d'obtenir une interface graphique puissante et simple à manier.

\subsection{Une progression rapide}

Comme décrit plus haut, nous n'avons pas attendu les premiers TP pour nous afférer à la tâche et avons commencé à \textit{bidouiller} la librairie LablGTK très tôt, lors de la semaine consacrée à la Recherche et à l'Innovation.

Ci-dessous une première ébauche d'interface graphique, réalisée environ une semaine après le début du développement de notre projet.

\begin{center}
\includegraphics[scale=0.3]{interface1.jpg} 
\end{center}

Première ébauche d’interface... Soit une fenêtre brute avec une simple barre d'outils, encore bien déserte. Ce fut l'une des premières versions fonctionnelles de notre interface !

Cependant, la progression a suivi une courbe exponentielle, pour se retrouver en quelques heures à une interface complète et largement intuitive. Elle est présentée ci-dessous :

\vspace{1cm}

\begin{center}
\includegraphics[scale=0.25]{interface2.png}
%\caption{Page d'accueil du projet, accompagnée d'un rapide guide explicatif}
\end{center}


%\begin{figure}
\begin{center}
\includegraphics[scale=0.25]{interface3.png}
%\caption{Détection des couleurs de la carte et choix des altitudes}
\end{center}
%\end{figure}


%\begin{figure}
\begin{center}
\includegraphics[scale=0.25]{interface4.png}
%\caption{Calcul d'itinéraire au travers du périple de la carte}
\end{center}
%\end{figure}

\vspace{1cm}

La version finale intègre tout le contenu du projet (décrit dans la suite de ce document) et réagit parfaitement aux évènements utilisateurs. L'utilisation de \textit{barre de défilement} a été favorisée pour éviter de gérer d'éventuelles erreurs dans les entrées utilisateur.

Le concept est simple : l'utilisateur n'a qu'à suivre les étapes décrites, et dès lors qu'il en complète une, le programme passe automatiquement à la suivante en lui affichant l'onglet concerné ! Il est possible de revenir en arrière facilement par le panneau d'onglets disposé sur le haut de la fenetre.

Grâce à l'interface, l'utilisateur peut :

	\begin{itemize}
		\item créer un nouveau projet
		\item choisir la précision de l'échantillonnage
		\item activer/désactiver et régler la correction des artefacts
		\item définir ses points de départ et d'arrivée directement sur la carte
		\item indiquer les valeurs respectives de chaque altitude
		\item et bien plus encore\ldots
	\end{itemize}


\section{Pré-traitement de la carte}

\subsection{SDL - Simple Directmedia Layer}

Comme son nom l'indique, cette bibliothèque est une surcouche à l'OCaml permettant de faire du traitement de l'image simplement. De nombreuses fonctions (notamment de capture et de remplacement de pixels) sont livrées et rendues simples d'utilisation. C'est pourquoi, pour tout ce qui concerne le pré-traitement de la carte, nous avons eu recours à la librairie SDL. Elle est libre, gratuite, bien documentée, et surtout très intuitive (de par ses noms de fonctions explicites).

%\begin{figure}
\begin{center}
\includegraphics[scale=0.25]{logosdl.png}
\end{center}
%\end{figure}

\subsection{Principe et usage}

Le pré-traitement de la carte est nécessaire et indispensable ; il s'agit de l'étape clé du projet. Cette étape permet de corriger les éventuels défauts de la carte, de la parcourir intégralement ou en partie (selon le souhait de l'utilisateur), voire meme d'en saisir certains pixels bien particuliers en vue de créer un fichier *.OBJ (comme par hasard).

Nous avons, tout au long du projet, géré notre carte comme une matrice de pixels, sur lesquels étaient appliqués des traitements plus ou moins précis et optimisés. De la correction du bruit à la génération d'un fichier tridimensionnel, le pré-traitement de l'image est l'acteur principal de toutes les étapes !

\subsection{Une carte basse résolution ? De mauvaise qualité ?}

Comme dans tout développement d'un programme destiné à un utilisateur lambda, nous considérons ce dernier comme un \textit{pur boulet}. Ainsi, il a fallu gérer le cas d'une carte mal scannée et surtout de mauvaise qualité -- bruit rémanent sur de nombreux pixels. Nous avons donc mis en place une correction permettant de régler la force du lissage ainsi que la précision. 

Deux algorithmes sont alors utilisés, l'un fait maison, l'autre issu du très célèbre filtre médian. Une chose essentielle est de savoir que, meme si l'utilisateur est confronté à une carte colorée, notre programme gère toutes les étapes par des niveaux de gris. L'avantage ? Une seule composante par couleur, plus pratique pour appliquer des tris ou des approximations.

\subsection{L'algorithme maison}

Lors de la détection des contours, l'algorithme détecte les changements de couleur. Comment ? Par des composantes différentes d'un pixel à l'autre. Seulement, un simple petit artefact peut parfois faire apparaitre une nouvelle couleur, impossible à discerner à l'oeil nu mais pourtant prise en compte par le programme.

L'utilisateur a donc la possibilité de régler la tolérance. Plus elle est élevée, plus la différences de teinte entre deux pixels voisins doit etre importante pour marquer un changement de couleur.

\subsection{Le filtre médian}

Ce filtre est l'un des plus connus pour l'élimination du bruit. Dans notre programme, il est systématiquement appliqué à l'image traitée, car il s'agit d'un phénomène nuisible qui n'est jamais provoqué de manière volontaire -- à la différence des faibles nuances de teintes, qui peuvent être proboquées.

Le principe est simple : pour chaque pixel de l'image, l'ensemble des pixels qui lui sont adjacents sont ajoutés à une liste, ensuite triée (généralement par ordre croissant/décroissant). Le pixel central est alors remplacé par l'élément central (l'élément médian) de la liste triée.


\subsection{Quadrillage d'échantillonnage}

Conformément au cahier des charges, et dans un souci de liberté pour l'utilisateur, il est possible de régler la finesse de l'échantillonnage. Ainsi, un traitement sera plus précis si un pixel sur deux est échantillonné, que dans le cas d'un pixel sur dix ; cependant, il sera également plus couteux et parfois disproportionné d'appliquer un échantillonnage aussi précis.

\begin{center}
\includegraphics[scale=0.25]{quadrillage1.png}
%\caption{Page d'accueil du projet, accompagnée d'un rapide guide explicatif}
\end{center}

C'est pourquoi la largeur du \textit{maillage} est paramétrable. Pour montrer à l'utilisateur l'échelle choisie, un quadrillage est rajouté sur sa carte, aussi bien horizontalement et verticalement que sur les diagonales.

\begin{center}
\includegraphics[scale=0.25]{quadrillage2.png}
%\caption{Page d'accueil du projet, accompagnée d'un rapide guide explicatif}
\end{center}


\subsection{Tracé des contours et détection des couleurs}

Toujours selon le pas de ce quadrillage, une double boucle se charge de parcourir l'ensemble des points importants (point important : point disposé sur les intersections du quadrillage) de la carte. Lorsqu'il détecte une différence de teinte supérieur au seuil de tolérance, il marque le pixel concerné et son voisin d'une tâche \textit{noire}, et ajoute immédiatement la nouvelle couleur à la liste finale.

Cependant, nous ne sommes pas à l'abris de doublons. Ainsi, à chaque détection d'une nouvelle couleur, la liste est triée puis analysée en vue de supprimer les couleurs rémanentes.

Plus la précision est élevée, plus le rendu sera détaillé, mais plus les opérations de modélisation tridimensionnelle seront longues.


\section{Modes d'échantillonnage}

Parce que l'équipe de LMTW ne souhaite pas développer un produit figé et abrupt, nous avons mis en place plusieurs modes d'échantillonnage. Ceci nous permet d'offrir à l'utilisateur un rendu toujours plus réaliste !

\subsection{Mode standard - colorisation respective}

Ce mode est celui imposé par le cahier des charges du projet. Il échantillonne chaque couleur de la carte, demande à l'utilisateur de renseigner les altitudes respectives pour chacune d'entre elle, puis génère un fichier 3D aux contours secs et abrupts.

La précision est grande, mais l'aspect esthétique s'en trouve quelque peu gaché. Les puristes de la cartographie y trouveront leur compte !

\begin{center}
\includegraphics[scale=0.25]{mode1.png}
\end{center}


\begin{center}
\includegraphics[scale=0.25]{mode2.png}
\end{center}


\subsection{Mode dégradé - lissage des contours}

Pour les plus novices, souhaitant avant tout obtenir un résultat esthétiquement réussi, nous avons intégré un mode \textit{dégradé}, comprenant un lissage total de la carte.

Le principe repose sur les célèbres \textit{height maps} : la carte est transformée en niveaux de gris -- par moyennage des trois composantes -- puis subit un flou gaussien -- étape de lissage. L'utilisateur entre la valeur du blanc -- (255,255,255) -- et du noir -- (000,000,000). De là, le programme se charge de déterminer l'altitude de chaque point en fonction de sa couleur et des altitudes extrêmes renseignées juste avant.

\vspace{1cm}

\begin{center}
\includegraphics[scale=0.5]{mode3.png}
\end{center}

\vspace{1cm}

\newpage

\section{Calcul d'itinéraire - Chemin le plus "rapide"}

Dans l'optique où ce projet pourrait servir à prévoir de futures randonnées, nous avons pensé bon d'intégrer un algorithme de recherche du plus "rapide" chemin. Car oui, la contrainte ici n'est pas uniquement matérielle (murs, vide, etc.)

\subsection{Les contraintes}

Dans le cas d'une telle carte, la principale contrainte concerne le dénivelé. Pour notre algorithme, nous considérons qu'un dénivelé abrupt supérieur à 30 unités est infranchissable, mais qu'au-deçà, il est franchissable.

Sur cette base, l'algorithme permet de savoir s'il vaut mieux contourner la montagne ou l'escalader pour se rendre de l'autre coté... Il s'agit d'un algorithme A* -- que nous ne présentons plus tant sa renommée est grande -- adapté à notre cas particulier d'un relief montagneux.

Il a été conçu en C puis interfacé avec l'OCaml. Cependant, pour des raisons techniques, nous ne pouvons pas le montrer en pratique lors de cette première soutenance\ldots

\subsection{Informations utiles}

Les informations qu'il indique à l'utilisateur sont les suivantes :

\begin{itemize}
	\item faisabilité ou non du trajet
	\item chemin le plus rapide
	\item dénivelé positif et négatif
	\item dénivelé global de la marche
	\item temps de parcours estimé
\end{itemize}

\subsection{Tracé de segments avec Bresenham}

Pour indiquer de manière visuelle le plus rapide chemin à l'utilisateur, rien de plus pratique qu'un ensemble de segments. Seulement, nous avons choisi de tracer les segments nous-mêmes, sans nous aider de la SDL, par simple curiosité.

De là, nous avons compris que tracer un segment \textit{réaliste} sur des pixels carrés n'est pas chose aisée. Un algorithme simple et léger donne de bons résultats : l'algorithme de \textsc{Bresenham}.

\begin{quote}
\textit{L’algorithme détermine quels sont les points d’un plan discret qui doivent être tracés afin de former une approximation de segment de droite entre deux points donnés.}
Wikipédia
\end{quote}


\vspace{1cm}

\begin{center}
\includegraphics[scale=0.5]{bresenham.png}
\end{center}

\vspace{1cm}

Nous ne présenterons pas ici l'algorithme en détails, mais nous avons tout de même souhaité le mentionner ; ce fut en effet intérressant d'apprendre à quel point un simple tracé de segments pouvait se révéler être "compliqué".

\newpage

\section{Un soupçon de 3D - le format OBJ}

Comme demandé dans le cahier des charges, notre programme génère un fichier texte au format *.OBJ \footnote{http://en.wikipedia.org/wiki/Wavefront\_.obj\_file - Wikipédia EN}. Il s'agit d'un format très répandu dans le monde de la 3D et interprété par de nombreux logiciels de modélisation tridimensionnelle, ce qui nous permet de tester notre échantillonnage sans même avoir conçu notre moteur graphique.

\subsection{La structure du .OBJ}

Un fichier .OBJ est un simple fichier texte possédant une structure un peu particulière. On commence par définir les coordonnées de tous nos points, avec à chaque fois le préfixe "v". Les points sont implicitement numérotés de 1 à \textit{n}.

\begin{verbatim}
v 0.1 0.1 1.0
v 0.6 3.4 3.2
v 2.3 0.2 0.9
\end{verbatim}

A la suite de la définition des points, il convient de définir les faces, en indiquant des triplets de points (selon leur numérotation implicite). Chaque ligne est préfixée d'un "f".

\begin{verbatim}
f 1 2 3
f 3 2 1
f 1 3 2
f 2 1 4
\end{verbatim}


\subsection{Modélisation de la carte}

Pour modéliser notre carte, nous allons utiliser un algorithme maison particulièrement simple. Après avoir parcouru de long en large notre carte, selon le pas défini par l'utilisateur, et avoir ajouté chaque point \textit{important} à notre matrice, nous écrivons les coordonnées de chaque point dans le fichier .OBJ. La première étape est résolue.

La plus délicate concerne les faces. Comme tout modèle 3D, notre carte devra comporter un ensemble de vertices (repérées par des triplets de coordonnées), elles-mêmes définissant les faces. Supposons un parcours séquentiel de la carte, selon l'abscisse x et l'ordonnée y. Pour chaque point, nous ajoutons les faces suivantes, qui formeront deux triangles et donc une face complète :

\begin{verbatim}
f (x*y) (x*y+1) (x*(y+1))
f (x*y) (x*(y+1)) ((x+1)*y)
\end{verbatim}

Ainsi, ces opérations se voient être répétées autant de fois que nécessaire, jusqu'à pouvoir produire des fichiers .OBJ de plus de 45 Mo -- pour une image haute résolution finement échantillonnée.

Une fois le fichier généré, nous pouvons, comme dit précédemment, l’ouvrir avec Blender par exemple. Bien entendu il ne s’agit que d’une étape intermédiaire, car un peu de travail reste encore avant de posséder notre propre moteur 3D capable de pouvoir lire ce fichier .OBJ et de se passer de logiciel tiers.

Rendez-vous dans deux mois pour l'aperçu de notre moteur graphique... \ldots

\newpage

\section{LablGL \& moteur graphique 3D}

Après s'être muni d'une interface graphique et d'un pré-traitement solides, nous avons quelque peu amorcé la phase de développement du moteur 3D.

\subsection{Les concepts 3D}

Parce que la 3D repose sur quelque principes fondamentaux -- vertices, faces, caméra -- nous avons trouvé bon de faire un rappel dessus. Durant son projet de SUP, Hervé (Sweepy) avait eu affaire à beaucoup de 3D, ce qui nous a conféré un véritable avantage quant à la gestion des caméras.

Après un cours sur le raw, le pitch, et bien plus encore, nous avons débuté le travail sur le moteur de rendu 3D.

\subsection{Le choix de la bibliothèque}

Nous avons choisi LablGL pour plusieurs raisons ; tout d'abord, elle est l'une des plus documentées (bien que sa documentation officielle reste très succincte). Ensuite, en tant que binding d'Open-GL pour OCaml, elle conserve les mêmes noms de méthodes qu'Open-GL en C ; autrement dit, il nous est possible de trifouiller dans de la documentation C pour trouver des pistes en cas de problème.

A cela s'ajoute son côté intuitif : en effet, elle est très pratique et dispose de nombreuses \textit{features} intéressantes, comme l'ajout de sources lumineuses et certains procédés de texturage.

\subsection{Avancement actuel}

Nous avons décidé de ne pas présenter notre ébauche durant cette soutenance, car jugée trop peu avancée et instable. Cependant, nos premières recherches -- à la date du rendu -- avaient débouché sur la création d'un mini-projet offrant des rotations continuelles de triangles.

\vspace{1cm}

\begin{center}
\includegraphics[scale=0.5]{moteurgraphique1.png}
\end{center}

\vspace{1cm}

\section{Informations pratiques}

\subsection{Site Internet}

Le projet LMTW n'échappe pas à la règle et possède son propre site Internet. Cependant, motivé par Hervé, nous avons rédigé plusieurs tutoriaux pour aider nos camarades de promotion dans leur création d'interface. De ce fait, le site -- propulsé par WordPress -- ne contient pas systématiquement d'actualités du projet !

\vspace{1cm}

\begin{center}
\includegraphics[scale=0.3]{site1.png}
\end{center}

\vspace{1cm}

\begin{center}
\includegraphics[scale=0.3]{site3.png}
\end{center}

\vspace{1cm}

\Large{\textbf{Rendez-vous sur :~\\http://aventureweb.com/projetcarto/}}

\newpage

\section{Conclusion}

Pour conclure sur ce tout nouveau projet, \textbf{Let's Map The World}, nous sommes à l'heure actuelle fiers de présenter ce projet au jury ! Il nous permet de réaliser à quel point l'OCaml est un outil puissant, mais surtout les nombreux domaines d'application du langage et de ses différentes librairies.

Le projet a un aspect très ludique et pratique à la fois, ce qui nous motive d'autant plus. Nous espérons pouvoir vous présenter un rendu à la hauteur pour notre soutenance finale, en Décembre !

\vspace{4cm}

\textbf{"Powered by LMTW Team"}

\end{document}